package leetcode.nod;

public class Lc427 {


    public Node construct(int[][] grid) {
        return getTreeRoot(grid, 0, grid.length - 1, 0, grid.length - 1);
    }


    public boolean isLeaf(int[][] grid, int xs, int xe, int ys, int ye) {
        int val = grid[xs][ys];
        for (int i = xs; i <= xe; i++) {
            for (int j = ys; j <= ye; j++) {
                if (grid[i][j] != val)
                    return false;
            }
        }
        return true;
    }
    public Node getTreeRoot(int[][] grid, int xs, int xe, int ys, int ye) {
        if (isLeaf(grid, xs, xe, ys, ye)) {
            return new Node(grid[xs][ys] == 1 ? true : false, true, null, null, null, null);
        }
        Node topLeft = getTreeRoot(grid, xs, (xs + xe) / 2, ys, (ys + ye) / 2);
        Node topRight = getTreeRoot(grid, xs, (xs + xe) / 2, (ys + ye) / 2 + 1, ye);
        Node bottomLeft = getTreeRoot(grid, (xs + xe) / 2 + 1, xe, ys, (ys + ye) / 2);
        Node bottomRight = getTreeRoot(grid, (xs + xe) / 2 + 1, xe, (ys + ye) / 2 + 1, ye );
        Node root = new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
        return root;
    }

}

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;


    public Node() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }

    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }

    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
}